package gold.digger;

import gold.utils.InputUtil;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1089 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {

        public void duplicateZeros(int[] arr) {
            int n = arr.length, l = 0, r = n - 1;
            // 双指针：l从头开始往右，r从尾开始往左，找到最终要淘汰多少个元素
            while (l < r) if (arr[l++] == 0) r--;
            if (r == n - 1) return;
            // r后面的元素是要淘汰的
            if (l == r) {
                r = n - 1;
                arr[r--] = arr[l--];
            } else {
                l = r;
                r = n - 1;
            }
            // 再次双指针往左运动：l往左遍历，将元素发送到r位置
            while (l >= 0) {
                if (arr[l] == 0) { // 复制，发送2个0给r
                    arr[r] = arr[r - 1] = 0;
                    r -= 2;
                } else { // 不复制，直接发送[l]给r
                    arr[r--] = arr[l];
                }
                l--;
            }
        }

        public void duplicateZeros_Fuck_Debug(int[] arr) {
            int n = arr.length, l = 0, r = n - 1;
            // 双指针：l从头开始往右，r从尾开始往左，找到最终要淘汰多少个元素
            while (l < r) if (arr[l++] == 0) r--;
            if (r == n - 1) return;
            // r后面的元素是要淘汰的
            l = r;
            r = n - 1;
            while (l >= 0) {
                if (l >= r) break;
                arr[r--] = arr[l--];
                if (arr[l + 1] == 0 && r >= 0) arr[r--] = 0;
            }
            System.out.println("t");
        }
    }

    public void run() {
        new Solution().duplicateZeros(InputUtil.toIntegerArray("[1,0,2,3,0,4,5,0]"));
//        new Solution().duplicateZeros(InputUtil.toIntegerArray("[1,2,3]"));
//        new Solution().duplicateZeros(InputUtil.toIntegerArray("[0,0,0,0,0,0,0]"));
//        new Solution().duplicateZeros(InputUtil.toIntegerArray("[8,4,5,0,0,0,0,7]"));
        new Solution().duplicateZeros(InputUtil.toIntegerArray("[1,5,2,0,6,8,0,6,0]"));
    }

    public static void main(String[] args) throws Exception {
        LC1089 an = new LC1089();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
